package everyday;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/21 21:44
 * 611. 有效三角形的个数
 * https://leetcode.cn/problems/valid-triangle-number/
 */
public class Solution611 {

    // 单调性 + 双指针
    public int triangleNumber(int[] nums) {
        // 先对数组进行排序, 保证单调性
        Arrays.sort(nums);
        // 若 a <= b <= c & a + b > c 说明可以组成三角形
        int n = nums.length;
        int ret = 0;
        // 先固定 c
        for (int i = n - 1; i >= 2; --i) {
            // 利用单调性和双指针枚举 a b, 并统计可以构成三角形的结果树
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    // 如果能构成三角形
                    ret += right - left;
                    --right;
                } else {
                    // 如果不能构成三角形
                    ++left;
                }
            }
        }
        // 返回结果
        return ret;
    }
}
